#ifndef CGRAPH_H_INCLUDED
#define CGRAPH_H_INCLUDED
#include <vector>
#include <memory>
#include <map>
#include <stack>
#include <limits>
using namespace std;

template <typename _VertexType, typename _EdgeType>
class CGraph
{
public:

   typedef _VertexType VertexType;
   typedef _EdgeType EdgeType;
   typedef typename vector<VertexType>::iterator VertexListIterator;
   typedef typename vector<unique_ptr<EdgeType>>::iterator EdgeMatrixIterator;
   class CEdgeIterator;

   class CVertexIterator
   {
    public:

        CVertexIterator() {}
        CVertexIterator(const CVertexIterator&);
        CVertexIterator(const CGraph<VertexType, EdgeType>*, const typename vector<VertexType>::iterator&);
        CVertexIterator(const CGraph<VertexType, EdgeType>*, int vertexNum = 0);
        ~CVertexIterator() {}

        VertexType& operator *();
        const VertexType& operator *() const;

        CEdgeIterator GetOutgoingEdgesBegin();
        const CEdgeIterator GetOutgoingEdgesBegin() const;
        CEdgeIterator GetOutgoingEdgesEnd();
        const CEdgeIterator GetOutgoingEdgesEnd() const;

        CVertexIterator& operator =(const CVertexIterator&);
        CVertexIterator& operator ++();

        int GetIndexOfCurrentVertex() const;

        bool operator <(const CVertexIterator& other) const;
        bool operator ==(const CVertexIterator&) const;
        bool operator !=(const CVertexIterator& other) const {return !operator ==(other);};

   private:

        const CGraph<VertexType, EdgeType>* graphPointer;
        VertexListIterator vertexListIterator;
   };


   class CEdgeIterator
   {
   public:

       CEdgeIterator() {};
       CEdgeIterator(const CEdgeIterator&);
       CEdgeIterator(const CGraph<VertexType, EdgeType>*, const EdgeMatrixIterator&);
       ~CEdgeIterator() {};

       EdgeType& operator*();
       const EdgeType& operator*() const;

       CVertexIterator GetBeginVertex();
       const CVertexIterator GetBeginVertex() const;
       CVertexIterator GetEndVertex();
       const CVertexIterator GetEndVertex() const;

       CEdgeIterator& operator =(const CEdgeIterator& other);
       CEdgeIterator& operator ++();

       bool operator ==(const CEdgeIterator& other) const;
       bool operator !=(const CEdgeIterator& other) const { return !operator==(other); };

   private:

       const CGraph<VertexType, EdgeType>* graphPointer;
       EdgeMatrixIterator edgeMatrixIterator;
   };

    CGraph(int vertexNum = 0);
    CGraph(VertexType vertexZeroVal, EdgeType edgeZeroVal, int vertexNum = 0);
    ~CGraph() {};

    CVertexIterator addVertexWeight(int vertexNum, const VertexType& value);
    CEdgeIterator addEdge(int from, int to, const EdgeType& weight);

    CVertexIterator GetVertexListBegin();
    CVertexIterator GetVertexListEnd();

    CEdgeIterator GetEdgeListBegin();
    CEdgeIterator GetEdgeListEnd();

    int GetVertexCount() const;
    EdgeType GetEdgeTypeZeroValue() const { return edgeTypeZeroValue; }
    VertexType GetVertexTypeZeroValue() const { return vertexTypeZeroValue; }

    bool existsEdge(int i) const
    {
        return matrix[i] != nullptr;
    }

private:

    VertexType vertexTypeZeroValue;     // нулевое значение для типа вершины
    EdgeType edgeTypeZeroValue;         // нулевое значение для типа ребра
    int vertexNumber;                   // число вершин
    vector<VertexType> vertexList;      // список вершин
    vector<unique_ptr<EdgeType>> matrix;// матрица смежности

};

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CVertexIterator::CVertexIterator(const CVertexIterator& other)
{
    this->vertexListIterator = other.vertexListIterator;
    this->graphPointer = other.graphPointer;
}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CVertexIterator::CVertexIterator(const CGraph<VertexType, EdgeType>* graph,
                                                               int vertexNum)
: graphPointer(graph)
{
    this->vertexListIterator = const_cast<CGraph<VertexType, EdgeType>*>(graph)->
    vertexList.begin() + vertexNum;

}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CVertexIterator::CVertexIterator(const CGraph<VertexType, EdgeType>* graph,
                                                               const typename vector<VertexType>::iterator& iter)
: graphPointer(graph), vertexListIterator(iter)
{}

template <typename VertexType, typename EdgeType>
VertexType& CGraph<VertexType, EdgeType>::CVertexIterator::operator*()
{
    return *vertexListIterator;
}

template <typename VertexType, typename EdgeType>
const VertexType& CGraph<VertexType, EdgeType>::CVertexIterator::operator*() const
{
    return *vertexListIterator;
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator CGraph<VertexType, EdgeType>::
                      CVertexIterator::GetOutgoingEdgesBegin()
{
    int vertexIndex = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->
                               GetVertexListBegin().vertexListIterator, this->vertexListIterator);

    for (int i = vertexIndex * graphPointer->GetVertexCount();
             i < (vertexIndex + 1) * graphPointer->GetVertexCount(); ++i)
         {
             if (graphPointer->matrix[i] != nullptr)
             {
                 return CGraph<VertexType, EdgeType>::CEdgeIterator(graphPointer,
                                   const_cast<CGraph<VertexType, EdgeType>*>
                                   (graphPointer)->matrix.begin() + i);
             }
        }

    return CGraph<VertexType, EdgeType>::CEdgeIterator(this->graphPointer,
                                                       const_cast<CGraph<VertexType, EdgeType>*>
                                                       (this->graphPointer)->matrix.begin() +
                                                       (vertexIndex + 1) * graphPointer->GetVertexCount());
}

template <typename VertexType, typename EdgeType>
const typename CGraph<VertexType, EdgeType >::CEdgeIterator CGraph<VertexType, EdgeType>::
                      CVertexIterator::GetOutgoingEdgesBegin() const
{
    int vertexIndex = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->
                               GetVertexListBegin().vertexListIterator, this->vertexListIterator);

    for (int i = vertexIndex * this->graphPointer->GetVertexCount();
             i < (vertexIndex + 1) * this->graphPointer->GetVertexCount(); ++i)
    {
        if (this->graphPointer->matrix[i] != nullptr)
        {
            return CGraph<VertexType, EdgeType>::CEdgeIterator(this->graphPointer,
                                                                const_cast<CGraph<VertexType, EdgeType>*>
                                                                (this->graphPointer)->matrix.begin() + i);
        }
    }

    return CGraph<VertexType, EdgeType>::CEdgeIterator(this->graphPointer,
                                                       this->graphPointer->matrix.begin() +
                                                       (vertexIndex + 1) * graphPointer->GetVertexCount());
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator CGraph<VertexType, EdgeType>::
                      CVertexIterator::GetOutgoingEdgesEnd()
{
    int vertexIndex = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->
                               GetVertexListBegin().vertexListIterator, this->vertexListIterator);

    return ++CGraph<VertexType, EdgeType>::CEdgeIterator(this->graphPointer,
                                                       const_cast<CGraph<VertexType, EdgeType>*>
                                                       (this->graphPointer)->matrix.begin() +
                                                       (vertexIndex + 1) * this->graphPointer->GetVertexCount());
}

template <typename VertexType, typename EdgeType>
const typename CGraph<VertexType, EdgeType>::CEdgeIterator CGraph<VertexType, EdgeType>::
                      CVertexIterator::GetOutgoingEdgesEnd() const
{
    int vertexIndex = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->
                               GetVertexListBegin().vertexListIterator, this->vertexListIterator);

    return ++CGraph<VertexType, EdgeType>::CEdgeIterator(this->graphPointer, this->graphPointer->matrix.begin() +
                                                       (vertexIndex + 1) * this->graphPointer->GetVertexCount());
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator&
CGraph<VertexType, EdgeType>::CVertexIterator::
    operator =(const CGraph<VertexType, EdgeType>::CVertexIterator& other)
{
    if (this->vertexListIterator != other.vertexListIterator)
    {
        this->vertexListIterator = other.vertexListIterator;
        this->graphPointer = other.graphPointer;
    }
    return *this;
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator&
CGraph<VertexType, EdgeType>::CVertexIterator::operator ++()
{
    ++vertexListIterator;
    return *this;
}

template <typename VertexType, typename EdgeType>
bool CGraph<VertexType, EdgeType>::CVertexIterator::
    operator <(const CVertexIterator& other) const
{
    return distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin(),
                    this->vertexListIterator)
        < distance(const_cast<CGraph<VertexType, EdgeType>*>(other.graphPointer)->vertexList.begin(),
                   other.vertexListIterator);
}

template <typename VertexType, typename EdgeType>
bool CGraph<VertexType, EdgeType>::CVertexIterator::
    operator == (const CGraph<VertexType, EdgeType>::CVertexIterator& other) const
{
    return (this->vertexListIterator == other.vertexListIterator);
}

template <typename VertexType, typename EdgeType>
int CGraph<VertexType, EdgeType>::CVertexIterator::GetIndexOfCurrentVertex() const
{
    return distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin(),
                    this->vertexListIterator);
}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CEdgeIterator::CEdgeIterator
(const CEdgeIterator& other)
{
    this->graphPointer = other.graphPointer;
    this->edgeMatrixIterator = other.edgeMatrixIterator;
}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CEdgeIterator::CEdgeIterator
(const CGraph<VertexType, EdgeType>* graph, const EdgeMatrixIterator& it)
{
    this->graphPointer = graph;
    this->edgeMatrixIterator = it;
}

template <typename VertexType, typename EdgeType>
EdgeType& CGraph<VertexType, EdgeType>::CEdgeIterator::operator*()
{
    return *(*edgeMatrixIterator);
}

template <typename VertexType, typename EdgeType>
const EdgeType& CGraph<VertexType, EdgeType>::CEdgeIterator::operator*() const
{
    return *(*edgeMatrixIterator);
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator CGraph<VertexType, EdgeType>::
    CEdgeIterator::GetBeginVertex()
{
    int edgeNumber = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->matrix.begin(),
                              this->edgeMatrixIterator);
    return CVertexIterator(this->graphPointer,
                           const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin() +
                           (edgeNumber / graphPointer->GetVertexCount()));
}

template <typename VertexType, typename EdgeType>
const typename CGraph<VertexType, EdgeType>::CVertexIterator CGraph<VertexType, EdgeType>::
    CEdgeIterator::GetBeginVertex() const
{
    int edgeNumber = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->matrix.begin(),
                              this->edgeMatrixIterator);
    return CVertexIterator(this->graphPointer,
                           const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin() +
                           (edgeNumber / graphPointer->GetVertexCount()));
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator CGraph<VertexType, EdgeType>::
    CEdgeIterator::GetEndVertex()
{
    int edgeNumber = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->matrix.begin(),
                              this->edgeMatrixIterator);
    return CVertexIterator(this->graphPointer,
                           const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin() +
                           (edgeNumber % this->graphPointer->GetVertexCount()));
}

template <typename VertexType, typename EdgeType>
const typename CGraph<VertexType, EdgeType>::CVertexIterator CGraph<VertexType, EdgeType>::
    CEdgeIterator::GetEndVertex() const
{
    int edgeNumber = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->matrix.begin(),
                              this->edgeMatrixIterator);
    return CVertexIterator(this->graphPointer,
                           const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->vertexList.begin() +
                           (edgeNumber % CGraph<VertexType, EdgeType>::vertexNumber));
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator& CGraph<VertexType, EdgeType>::
    CEdgeIterator::operator =(const CEdgeIterator& other)
{
    if (this->edgeMatrixIterator != other.edgeMatrixIterator)
    {
        this->graphPointer = other.graphPointer;
        this->edgeMatrixIterator = other.edgeMatrixIterator;
    }
    return *this;
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator& CGraph<VertexType, EdgeType>::
    CEdgeIterator::operator ++()
{
    int edgeNumber = distance(const_cast<CGraph<VertexType, EdgeType>*>(this->graphPointer)->matrix.begin(), this->edgeMatrixIterator);

    ++this->edgeMatrixIterator;
    ++edgeNumber;

    while ((*(this->edgeMatrixIterator) == nullptr) && (edgeNumber <this->graphPointer->GetVertexCount() * this->graphPointer->GetVertexCount()))
    {
        ++this->edgeMatrixIterator;
        ++edgeNumber;
    }

    return *this;
}

template <typename VertexType, typename EdgeType>
bool CGraph<VertexType, EdgeType>::CEdgeIterator::
    operator==(const CGraph<VertexType, EdgeType>::CEdgeIterator& other) const
{
    return (this->edgeMatrixIterator == other.edgeMatrixIterator);

}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CGraph(int vertexNum)
{
    vertexNumber = vertexNum;
    vertexList.resize(vertexNum);
    matrix.resize(vertexNum * vertexNum);
}

template <typename VertexType, typename EdgeType>
CGraph<VertexType, EdgeType>::CGraph(VertexType vertexZeroVal, EdgeType edgeZeroVal, int vertexNum)
: edgeTypeZeroValue(edgeZeroVal), vertexTypeZeroValue(vertexZeroVal), vertexNumber(vertexNum)
{
    vertexList.assign(vertexNum, vertexTypeZeroValue);
    matrix.resize(vertexNum * vertexNum);
    for (int i = 0; i <matrix.size(); ++i)
    {
        matrix[i] = nullptr;
    }
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator
CGraph<VertexType, EdgeType>::addVertexWeight(int vertexNum, const VertexType& value)
{
    //if (vertexNum >= vertexNumber || vertexNum <0)
    //{
    //    throw invalid_argument("Invalid vertex!\n");
    //}
    vertexList[vertexNum] = value;
    return CGraph<VertexType, EdgeType>::CVertexIterator(this, vertexList.begin() + vertexNum);
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator
CGraph<VertexType, EdgeType>::addEdge(int from, int to, const EdgeType& weight)
{
    //if ((from <0) || (to <0) || (from >= vertexNumber) || (to >= vertexNumber))
    //{
    //    throw invalid_argument("Invalid vertexes!\n");
    //}
    // среди кратных ребер оставляем ребро с наименьшим весом
    if (matrix[vertexNumber * from + to] != nullptr)
    {
        if (*matrix[vertexNumber * from + to] <weight)
        {
            return CEdgeIterator(this, matrix.begin() + vertexNumber * from + to);
        }
    }

    matrix[vertexNumber * from + to] = unique_ptr<EdgeType>(new EdgeType(weight));

    return CEdgeIterator(this, matrix.begin() + vertexNumber * from + to);
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator
CGraph<VertexType, EdgeType>::GetVertexListBegin()
{
    for (int i = 0; i <vertexNumber; ++i)
    {
        if (vertexList[i] != vertexTypeZeroValue)
        {
            return CVertexIterator(this, vertexList.begin() + i);
        }
    }
    return CVertexIterator(this, vertexList.end());
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CVertexIterator
CGraph<VertexType, EdgeType>::GetVertexListEnd()
{
    return CVertexIterator(this, vertexList.end());
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator
CGraph<VertexType, EdgeType>::GetEdgeListBegin()
{
    for (int i = 0; i <vertexNumber * vertexNumber; ++i)
    {
        if (matrix[i] != nullptr)
        {
            return CEdgeIterator(this, matrix.begin() + i);
        }
    }
    return CEdgeIterator(this, matrix.end());
}

template <typename VertexType, typename EdgeType>
typename CGraph<VertexType, EdgeType>::CEdgeIterator
CGraph<VertexType, EdgeType>::GetEdgeListEnd()
{
    return CEdgeIterator(this, matrix.end());
}

template <typename VertexType, typename EdgeType>
int CGraph<VertexType, EdgeType>::GetVertexCount() const
{
    return vertexNumber;
}

#endif // CGRAPH_H_INCLUDED
